The present invention relates to a bandwidth management method and apparatus for use in a connectionless IP (Internet Protocol) communication network or the like which is free from the necessity of setting a connection prior to the start of communication and, more particularly, a bandwidth management method and apparatus for a communication network which guarantees the minimum communication bandwidth.
In a connectionless communication network like the IP communication network, there are no end-to-end paths predetermined. In other words, it is not predetermined over which path the input datagram packet is to be routed through the network. Upon input of the packet to one node in the network, the node router refers to its forwarding table and determines the link to which the packet is to be sent next in accordance with the destination address contained in the header of the packet.
The forwarding table is determined by an SPF (Shortest Path First) scheme. SPF is a table for selecting a path that minimizes the total cost of weighted values of links between the input (source) and output (destination) nodes. Accordingly, packets from the same input node to the same output node are always routed through the network over the same path. Since the packet routing by SPF takes place irrespective of individual traffic, however, particular paths or links in the network may sometimes become so congested with packets that required packet routing is impossible to achieve, allowing them to be lost or missing.
As a solution to this problem, there is available an architecture called Diffserv (Differentiated Services) (IETF RFC2475). This architecture sets a plurality of priority service classes to treat services differently to enhance the quality of communication over the Internet. Of the services, an EF (Expedited Forwarding) class (IETF RFC2475) is a service class that guarantees each user's contracted bandwidth (transmission rate expressed in Mbits/sec, for instance). But it is the bandwidth for packet input that the user contracts, and the destination of the packet is unknown.
For example, in such an IP network ND as depicted in FIG. 1 which contains nodes ND1 to ND5 connected by links L12, L21, L13, L31, L14, L41, L15, L51, L23, L32, L25, L52, L34, L43, the nodes ND1, ND2, ND3 are used as edge nodes connected to user apparatuses U1, U2, U3 or other networks to form a Diffserv network DNW, in which a bandwidth guarantee for each user belonging to the EF class or assured forwarding class, for example, U1, is required for the packet input to the edge node ND1. In FIG. 1 the edge node ND1, for instance, is shown to have connected thereto one user apparatus U1, but in practice, plural user apparatuses are connected to the edge node. This applies to the other edge nodes and those in the network that embodies the present invention as described later on. In the connectionless data transfer as in Diffserv, since no particular path is preset, the destination node of the packet unknown until it is actually input to the network and its destination information is read.
To provide bandwidth guarantees for the Diffserv users, it is necessary to confirm the bandwidth to be guaranteed for all possible traffic patterns over the Diffserv network. In practice, however, candidates for destination edge nodes are as many as the edge nodes forming the network, and consideration needs to be taken of all possible patterns as to how much traffic flows to which edge node. Letting N represent the number of edge nodes and K the number of steps of the bandwidth for admissible traffic to each edge node, the number of input traffic patterns for all the edge nodes is (K+M−2)!/(N−2)!K!. For example, when N=5 and K=5, the number of traffic patterns for all edge nodes is as large as 565. In the actual network, the value N is far greater, and consequently, the number of possible traffic patterns further increases correspondingly; it is practically impossible to taken into account such an enormous number of traffic patterns.